package com.cheng.dataStructure.linkedlist;

import java.util.Stack;

/**
 * @User Administrator
 * @Classname Exercise
 * @Project Data-structure-and-algorithm
 * @Description  五个单链表面试题：
 * 1.求单链表中有效节点的个数(排除头结点)
 * 2.查找单链表中倒数第k个节点
 * 3.单链表的反转
 * 4.从尾到头打印单链表
 * 5.合并两个有序的单链表，合并完后任然有序
 * @Author wpcheng
 * @Create 2021-06-25-10:04
 * @Version 1.0
 */
public class Exercise {
    public static void main(String[] args) {
        //创建节点
        TestNode node1 = new TestNode(1);
        TestNode node2 = new TestNode(2);
        TestNode node3 = new TestNode(3);
        TestNode node4 = new TestNode(4);
        TestNode node5 = new TestNode(5);
        TestNode node6 = new TestNode(6);
        TestNode node7 = new TestNode(7);
        TestNode node8 = new TestNode(8);
        //创建链表
        TestSingleLinkedList list = new TestSingleLinkedList();
        TestSingleLinkedList list1 = new TestSingleLinkedList();
        //添加节点到链表
        list.addById(node1);
        list.addById(node2);
        list.addById(node7);
        list.addById(node8);

        list1.addById(node5);
        list1.addById(node6);
        list1.addById(node3);
        list1.addById(node4);


        list.listAll();

        //练习1.求单链表中有效节点的个数(排除头结点)
        System.out.println("有效节点个数为："+list.test1(list.getHead()));

        //练习2：查找单链表中倒数第k个节点
        System.out.println(list.test2(list.getHead(), 2));

        //练习3：反转单链表
        list.test3(list.getHead());
        //反转后的链表
        System.out.println("反转后的链表为：");
        list.listAll();

        //练习4：从尾到头打印单链表
        System.out.println("从尾到头打印单链表为：");
        list.test4(list.getHead());


    }

}

class TestSingleLinkedList{
    //定义头结点
    private TestNode head = new TestNode(0);

    public TestNode getHead() {
        return head;
    }

    /**
     * 练习1.求单链表中有效节点的个数(排除头结点)
     * 思路：直接遍历即可
     * @param head
     * @return length
     */
    public int test1(TestNode head){
        if (head.next == null){
            return 0;
        }
        int length = 0;
        TestNode temp = head.next;
        while (temp != null){
              length++;
              temp = temp.next;
        }
        return length;
    }

    /**
     * 练习2：查找单链表中倒数第k个节点
     * 思路分析：
     * 1.用练习1的方法得到链表有效长度size
     * 2.从头到尾遍历链表，遍历(size-k)次，就得到了倒数第k个节点
     * @param head 头结点
     * @param k 倒数第k个节点
     * @return TestNode
     */
    public TestNode test2(TestNode head,int k){
        //如果链表为空
        if(head.next == null){
            return null;
        }
        //得到链表有效长度size
        int size = test1(head);

        //确定k的范围
        if (k <= 0 || k > size){
            return  null;
        }
        TestNode temp = head.next;
        for (int i = 0; i < size-k; i++) {
            temp = temp.next;
        }
        return temp;
    }



    /**
     * 练习3：单链表反转：头插法
     * 1.定义一个新的头节点newTestNode，用来存放新链表
     * 2.定义辅助变量遍历链表，每遍历一个节点就把节点取出，放入newTestNode，放入位置在上一个遍历的节点的前面
     * 3.让原链表的head.next = newTestNode.next
     */
    public void test3(TestNode head){
        //如果链表为空或者只有一个节点，无需反转
        if (head.next == null || head.next.next == null){
            return;
        }
        //定义一个新的头节点newTestHead
        TestNode newTestHead = new TestNode(0);
        //定义辅助变量
        TestNode temp = head.next;
        //tempNext指向当前节点的下一个节点
        TestNode tempNext = null;
        //遍历链表
         while (temp != null){
             tempNext = temp.next;//保存当前节点的下一个节点
             temp.next = newTestHead.next;//将temp下一个节点的引用指向新链表，就是把temp的下一个节点放入链表最前端
             newTestHead.next = temp;//将temp.next指向temp，可以理解为将temp和temp.next的位置倒转了一下
             temp = tempNext;//temp后移

        }
        head.next = newTestHead.next;//将newTestHead对下一个节点的引用赋给head
    }


    /**
     * 练习4.从尾到头打印单链表
     * 思路：先遍历链表，把节点存入栈，再出栈
     * @param head
     */
    public void test4(TestNode head){
        if (head.next == null){
            return;
        }
        //创建一个栈，
        Stack<TestNode> stack = new Stack<TestNode>();
        TestNode temp = head.next;
        //将节点压入栈 push
        while (temp != null){
            stack.push(temp);
            temp = temp.next;
        }
        //将栈里的节点打印
        while (stack.size() > 0){
            System.out.println(stack.pop());
        }
    }






    //添加节点
    public void addById(TestNode testNode){
        //定义辅助变量
        TestNode temp = head;
        //定义标志位，如果为false，说明新节点的编号在链表中不存在，为true说明在链表中已经存在
        Boolean flag = false;
        while(true){
            //temp是链表的最后一个节点
            if (temp.next == null){
                break;
            }
            //插入位置确定
            if (temp.next.id > testNode.id){
                break;
            }
            //新节点的编号在链表中已经存在
            if(temp.next.id == testNode.id){
                flag = true;
                break;
            }
            temp = temp.next;
        }
        if (flag){
            System.out.println("新节点的编号"+testNode.id+"在链表中已经存在，插入失败");
        }else {
            testNode.next = temp.next;
            temp.next = testNode;
        }
    }

    //显示节点
    public void listAll(){
        //如果链表为空
        if (head.next==null){
            System.out.println("链表为空");
            return;
        }
        TestNode temp = head.next;
        while (true){
            if (temp == null){
                return;
            }
            System.out.println(temp);
            //每输出一个节点，就将temp后移一下，不然会陷入死循环，导致不能输出
            temp = temp.next;
        }
    }
}




class TestNode{
    public int id;
    public TestNode next;

    public TestNode(int id) {
        this.id = id;
    }

    @Override
    public String toString() {
        return "TestNode{" +
                "id=" + id +
                '}';
    }
}